/**
 *  @file dfs_scc.c
 *  @brief Depth-first search for directed graphs, using the
 *	   detailed algorithm of Cormen, Leiserson, and Rivest (Introduction to
 *	   Algorithms, first edition, p. 478); also can continue to find strongly
 *    connected components.  Based on 1991 version of dfs_d.c and subsumes it.
 *  @author Matt Stallmann
 *  @date March 2005
 *  $Id: dfs_scc.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 1991, 2005  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include <stdio.h>
#include <stdbool.h>            /* type bool, values true/false */
#include <assert.h>
#include "Gdr.h"

short color[ MAX_VERTEX ];     /* WHITE if unvisited, GRAY if on stack, BLACK
                                  if finished visit */
#define WHITE 0
#define GRAY 1
#define BLACK 2

int d[ MAX_VERTEX ];   /* time that vertex is discovered (preorder number) */
int f[ MAX_VERTEX ];     /* time that visit is finished (postorder number) */
int time_stamp;                 /* current time stamp */

 /* declarations and macros for the animation */
#define MSG_SIZE 100            /* maximum length of a message */
char msg[ MSG_SIZE ];
char answer[ MSG_SIZE ];
TWIN pwin;                      /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
                   hide_window(pwin))
#define COUNT 4

/* stack to keep track of vertices in reverse order of finishing first DFS */
vertex vertex_stack[ MAX_VERTEX ];
int vs_index = 0;

void vs_init( void ) {
  vs_index = 0;
}

bool vs_empty( void ) {         /* use int if <stdbool.h> unavailable */
  return vs_index == 0;
}

void vs_push( vertex v ) {
  assert( vs_index < MAX_VERTEX );
  vertex_stack[ vs_index++ ] = v;
}

vertex vs_pop( void ) {
  assert( vs_index > 0 );
  --vs_index;
  return vertex_stack[ vs_index ];
}

/* end of vertex stack ADT */

void DFS_Visit( vertex u )
{
  vertex v;                     /* current other vertex in adjacency list */
  edge e;                       /* current edge in adjacency list */

  color[ u ] = GRAY;
  d[ u ] = time_stamp = time_stamp + 1;

  expose_vertex_label( u );
  sprintf( msg, "%d/", d[ u ] );
  change_vertex_label( u, msg );
  sprintf( msg, "Start visit, vertex %d\nClick Resume to continue", u );
  wait( msg );

  for_adjacent( u, e, v ) {
    blink_edge( e, COUNT );
    if( color[ v ] == WHITE ) { /* tree edge */
      hide_edge_label( e );
      highlight_edge( e );
      DFS_Visit( v );
    }
    else if( color[ v ] == GRAY ) { /* back edge */
      expose_edge_label( e );
      change_edge_label( e, "B" );
    }
    else if( d[ u ] < d[ v ] ) {	/* forward edge */
      expose_edge_label( e );
      change_edge_label( e, "F" );
    }
    else { /* d[u] > d[v] -- cross edge */
      expose_edge_label( e );
      change_edge_label( e, "C" );
    }
  }
  vs_push( u );
  color[ u ] = BLACK;
  f[ u ] = time_stamp = time_stamp + 1;

  un_highlight_vertex( u );
  sprintf( msg, "%d/%d", d[ u ], f[ u ] );
  change_vertex_label( u, msg );

  sprintf( msg, "End visit, vertex %d\nClick Resume to continue", u );
  wait( msg );
} /* end, DFS_Visit */

void reverse_DFS_Visit( vertex u, char component_label )
{
  vertex v;                     /* current other vertex in adjacency list */
  edge e;                       /* current edge in adjacency list */

  color[u] = GRAY;

  expose_vertex_label( u );
  sprintf( msg, "[%c]", component_label );
  change_vertex_label( u, msg );
  sprintf( msg, "Adding vertex %d to component\nClick Resume to continue",
           u );
  wait( msg );

  for_incoming_edges( u, e, v ) { /* note: INCOMING edges */
    blink_edge( e, COUNT );
    if( color[v] == WHITE ) { /* tree edge */
      hide_edge_label( e );
      highlight_edge( e );
      reverse_DFS_Visit( v, component_label );
    }
    else if (color[v] == GRAY) { /* back edge */
      un_highlight_edge( e );
      hide_edge_label( e );
    }
    else { /* not a tree edge or back edge */
      un_highlight_edge( e );
      hide_edge_label( e );
      hide_edge( e );
    }
  }
  color[u] = BLACK;
  un_highlight_vertex( u );
  sprintf( msg, "End visit, vertex %d\nClick Resume to continue", u );
  wait( msg );
} /* end, reverse_DFS_Visit */

void DFS( void ) {              /* with optional SCC algorithm */
  vertex u;
  edge e;

  /* initialize the animation */
  for_all_vertices( u ) {
    highlight_vertex( u );
    hide_vertex_label( u );
  }
  for_all_edges( e ) {
    un_highlight_edge( e );
    hide_edge_label( e );
  }
  init_prompt_window;

  /* initialize algorithm data */
  vs_init();
  for_all_vertices( u ) {
    color[ u ] = WHITE;
  }
  time_stamp = 0;

  /* do outer loop of initial DFS */
  write_text_window( pwin,
                     "Select vertex for starting DFS\ntype `q` to quit" );
  while( (u = select_vertex()) != NULL_VERTEX ) {
    if( color[ u ] == WHITE ) {
      DFS_Visit( u );
      write_text_window( pwin,
                         "Select another starting vertex\ntype `q` to quit" );
    }
    else {
      hide_window( pwin );
      write_text_window( pwin, "Vertex already visited, try again" );
    }
  }
  query( 0, 0, "End of first depth-first search; find SCC's? (y/n) ", answer );

  if( answer[ 0 ] == 'y' ) {
    char component_label = 'A'; /* use capital letters to label components */

    /* remove highlighting from all edges (label tree edges with "+" */
    for_all_edges( e ) {
      if( is_highlighted_edge( e ) ) {
        un_highlight_edge( e );
        change_edge_label( e, "+" );
        expose_edge_label( e );
      }
    }

    /* reinitialize vertex colors and display accordingly */
    for_all_vertices( u ) {
      color[ u ] = WHITE;
      highlight_vertex( u );
    }
    
    /* initiate reverse visits in reverse (stack) order */
    while( ! vs_empty() ) {
      u = vs_pop();
      if( color[ u ] == WHITE ) {
        reverse_DFS_Visit( u, component_label++ );
      }
    }
    wait( "Algorithm done,\nclick RESUME to see the whole graph." );

    /* restore hidden edges */
    for_all_edges( e ) {
      if( ! is_displayed_edge( e ) ) {
        display_edge( e );
        hide_edge_label( e );
      }
      else {
        highlight_edge( e );
      }
    }
  }

  wait( "Click RESUME to restore graph." );

  /* reset all display characteristics to "normal" */

  for_all_vertices(u) {
    change_vertex_label( u, "" );
    hide_vertex_label( u );
    un_highlight_vertex( u );
  }
  for_all_edges( e ) {
    change_edge_label( e, "" );
    expose_edge_label( e );
    un_highlight_edge( e );
    display_edge( e );
  }
  destroy_prompt_window;
}

void animat(void) {DFS();}

/*  [Last modified: 2007 06 28 at 19:45:43 GMT] */
